package com.shixianjun.sort;

import com.shixianjun.tools.Tools;

public class _3_插入排序 implements Sortable {

    @Override
    public void sort(SortableElement[] arr) {
        sort3(arr);
    }

    void sort1(SortableElement[] arr) {
        for (int i = 1; i < arr.length; i++) {
            for (int j = i; j > 0 && arr[j].value < arr[j - 1].value; j--) {
                Tools.swap(arr, j, j - 1);
            }
        }
    }

    void sort2(SortableElement[] arr) {
        for (int i = 1; i < arr.length; i++) {
            SortableElement tem = arr[i];
            int index = i;
            for (int j = i; j > 0 && tem.value < arr[j - 1].value; j--) {
                index = j - 1;
                arr[j] = arr[j - 1];
            }
            arr[index] = tem;
        }
    }

    void sort3(SortableElement[] arr) {
        for (int i = 1, j; i < arr.length; i++) {
            SortableElement temp = arr[i];
            for (j = i; j > 0 && temp.value < arr[j - 1].value; j--) {
                arr[j] = arr[j - 1];
            }
            arr[j] = temp;
        }
    }
}
